/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-06-29 16:27:04
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-06-29 17:25:25
 * @FilePath     : \algorithm\countingSort.js
 * @Description  : 计数排序
 */
function countingSort(arr) {
  let max = Math.max(...arr)
  let index = 0
  let _temp = new Array(max + 1)
  for (let i = 0; i < arr.length; i++) {
    if (!_temp[arr[i]]) {
      _temp[arr[i]] = 0
    }
    _temp[arr[i]]++
  }
  for (let j = 0; j < _temp.length; j++) {
    while ( _temp[j] > 0) {
      arr[index++] = j
      _temp[j]--
    }
  }
  return arr
}

let a = [3, 3, 5, 6, 9, 9, 15, 15, 3, 3, 8]

console.log(countingSort(a))